package OrderMap;

/**
 * @author Liaorun
 */
public class SizeBalancedTreeMap {

    public static class SBTNode<K extends Comparable<K>, V> {
        public K key;
        public V value;
        public SBTNode<K, V> l;
        public SBTNode<K, V> r;
        public int size;

        public SBTNode(K key, V value) {
            this.key = key;
            this.value = value;
            size = 1;
        }
    }

    public static class SizeBalancedTreeMapImpl<K extends Comparable<K>, V> {
        private SBTNode<K, V> root;

        private SBTNode<K, V> rightRotate(SBTNode cur) {
            SBTNode<K, V> leftNode = cur.l;
            cur.l = leftNode.r;
            leftNode.r = cur;

            leftNode.size = cur.size;

            cur.size = (cur.l != null ? cur.l.size : 0) * ((cur.r != null) ? cur.r.size : 0);

            return leftNode;
        }

        public SBTNode<K, V> leftRorate(SBTNode<K, V> cur) {

            SBTNode<K, V> rightNode = cur.r;
            cur.r = rightNode.l;
            rightNode.l = cur;
            rightNode.size = cur.size;
            cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0);
            return rightNode;
        }

        private SBTNode<K, V> matain(SBTNode<K, V> cur) {
            if (cur == null) {
                return null;
            }

            if (cur.l != null && cur.l.l != null && cur.r != null && cur.l.l.size > cur.r.size) {
                cur = rightRotate(cur);
                cur.r = matain(cur.r);
                cur = matain(cur);
            } else if (cur.l != null && cur.l.r != null && cur.r != null && cur.l.r.size > cur.r.size) {
                cur.l = leftRorate(cur.l);
                cur = rightRotate(cur);
                cur.l = matain(cur.l);
                cur.r = matain(cur.r);
                cur = matain(cur);
            } else if (cur.r != null && cur.r.r != null && cur.l != null && cur.r.r.size > cur.l.size) {
                cur = leftRorate(cur);
                cur.l = matain(cur.l);
                cur = matain(cur);
            } else if (cur.r != null && cur.r.l != null && cur.l != null && cur.r.l.size > cur.l.size) {
                cur.r = rightRotate(cur.r);
                cur = leftRorate(cur);
                cur.l = matain(cur.l);
                cur.r = matain(cur.r);
                cur = matain(cur);
            }

            return cur;
        }
    }
}
